package x.y.z;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Interview_4_1_RouteBetweenNodes {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 邻接矩阵转化为邻接表
        ArrayList<Integer>[] G = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            G[i] = new ArrayList<>();
        }
        for (int[] g : graph) {
            G[g[0]].add(g[1]);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int head = queue.poll();
            if (G[head].contains(target)) {
                return true;
            }
            for (int node : G[head]) {
                queue.offer(node);
            }
        }
        return false;
    }
}
